package leetcode;

import java.util.HashSet;

public class Lc2707_2 {



    public int minExtraChar(String s, String[] dictionary) {
        int len = s.length();

        HashSet<String> set = new HashSet<>();
        for (int i = 0; i < dictionary.length; i++) {
            set.add(dictionary[i]);
        }

        //dp[i] 表示以字符i-1未结尾的最小值，如果存在 [j ~i)字符串在字典中，在dp[i] = min(dp[j]) ,所以要枚举j
        int[] dp = new int[len + 1];
        for (int i = 1; i <= len; i++) {
            dp[i] = dp[i-1] + 1; //初始化i为额外字符
            for (int j = i - 1; j >= 0; j--) {
                if (set.contains(s.substring(j, i))) {
                    dp[i] = Math.min(dp[i], dp[j]);
                }
            }
        }
        return dp[len];
    }

    public static void main(String[] args) {
        Lc2707_2 lc2707_2 = new Lc2707_2();


        String s = "leetscode";
        String[] ss = {"leet","code","leetcode"};
        System.out.println(lc2707_2.minExtraChar(s, ss));
    }

}
